/*-------------------------------------------------------------------------
 *
 * barrier.c
 *	  同步协作进程的障碍。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * 参考维基百科[1]：“在并行计算中，屏障是一种同步方法。
 * 一个线程或进程必须在此处停止，并且在所有其他线程/进程到达此屏障之前，
 * 不能继续执行。”
 *
 * 这种屏障的实现允许已知的静态参与者集，或参与者可以随时加入或离开
 * 的动态参与者集。在动态情况下，可以使用阶段号来跟踪并行算法的进展，
 * 当新参与者加入时，可能需要与多阶段算法的当前阶段同步。在静态情况下，
 * 阶段号在内部使用，但客户端代码不严格需要访问它，因为只有当声明的
 * 参与者数量到达屏障时，阶段才能推进，因此客户端代码对计算的当前阶段
 * 应始终毫无疑问。
 *
 * 考虑一个涉及计算阶段 A、B 和 C 的并行算法，其中每个阶段的输出在下一个阶段
 * 开始之前是必需的。
 *
 * 在静态屏障初始化为 4 个参与者的情况下，每个参与者在阶段 A 工作，
 * 然后调用 BarrierArriveAndWait 等待直到所有 4 个参与者都到达该点。
 * 当 BarrierArriveAndWait 返回控制时，每个参与者可以进行 B 计算，依此类推。
 * 因为屏障知道期望多少参与者，所以计算阶段不需要标签或编号，
 * 因为每个进程的程序计数器隐含了当前阶段。即使某些进程启动缓慢并开始
 * 运行阶段 A，其他参与者也在期待他们，并将在屏障处耐心等待。代码可以如下编写：
 *
 *     perform_a();
 *     BarrierArriveAndWait(&barrier, ...);
 *     perform_b();
 *     BarrierArriveAndWait(&barrier, ...);
 *     perform_c();
 *     BarrierArriveAndWait(&barrier, ...);
 *
 * 如果事先不知道参与者的数量，则需要动态屏障，在初始化时应将数量设置为零。
 * 由于参与者的附加和脱离，数量必然会随时间变化，因此阶段 B、C 或甚至处理结束
 * 可能在任何给定参与者开始运行并附加之前达到。因此，客户端代码必须在附加后
 * 对阶段号进行初始测试，因为它需要找出已附加的参与者达到的算法阶段，
 * 以便与该工作同步。一旦程序计数器或某种表示当前进展的方式与屏障的阶段
 * 同步，就可以像静态情况一样使用正常的控制流。我们的示例可以使用带有
 * falls-through 的 switch 语句编写，如下所示：
 *
 *     phase = BarrierAttach(&barrier);
 *     switch (phase)
 *     {
 *     case PHASE_A:
 *         perform_a();
 *         BarrierArriveAndWait(&barrier, ...);
 *     case PHASE_B:
 *         perform_b();
 *         BarrierArriveAndWait(&barrier, ...);
 *     case PHASE_C:
 *         perform_c();
 *         BarrierArriveAndWait(&barrier, ...);
 *     }
 *     BarrierDetach(&barrier);
 *
 * 静态屏障的行为类似于 POSIX 的 pthread_barrier_t。动态屏障的行为
 * 类似于 Java 的 java.util.concurrent.Phaser。
 *
 * [1] https://en.wikipedia.org/wiki/Barrier_(computer_science)
 *
 * IDENTIFICATION
 *	  src/backend/storage/ipc/barrier.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"
#include "storage/barrier.h"

static inline bool fc_BarrierDetachImpl(Barrier *fc_barrier, bool fc_arrive);

/*
 * 初始化这个屏障。要使用静态参与者数量，请提供每个阶段中等待的参与者数量，
 * 表示该数量的后端隐式连接。要使用动态参与者数量，请在此处指定零，
 * 然后使用BarrierAttach()和
 * BarrierDetach()/BarrierArriveAndDetach()显式注册和注销参与者。
 */
void BarrierInit(Barrier *fc_barrier, int fc_participants)
{
	SpinLockInit(&fc_barrier->mutex);
	fc_barrier->participants = fc_participants;
	fc_barrier->arrived = 0;
	fc_barrier->phase = 0;
	fc_barrier->elected = 0;
	fc_barrier->static_party = fc_participants > 0;
	ConditionVariableInit(&fc_barrier->condition_variable);
}

/*
 * 到达此屏障，等待所有其他附加参与者也到达
 * 然后返回。增加当前阶段。调用者必须已附加。
 *
 * 在等待期间，pg_stat_activity显示一个wait_event_type和wait_event，
 * 由传入的wait_event_info控制，应该是pgstat.h中定义的WaitEventXXX枚举之一的值。
 *
 * 在任意选择的一个参与者中返回true。在所有其他参与者中返回false。
 * 返回代码可用于选举一个参与者来执行必须串行完成的工作阶段，
 * 而其他参与者等待。
 */
bool BarrierArriveAndWait(Barrier *fc_barrier, uint32 fc_wait_event_info)
{
	bool		fc_release = false;
	bool		fc_elected;
	int			fc_start_phase;
	int			fc_next_phase;

	SpinLockAcquire(&fc_barrier->mutex);
	fc_start_phase = fc_barrier->phase;
	fc_next_phase = fc_start_phase + 1;
	++fc_barrier->arrived;
	if (fc_barrier->arrived == fc_barrier->participants)
	{
		fc_release = true;
		fc_barrier->arrived = 0;
		fc_barrier->phase = fc_next_phase;
		fc_barrier->elected = fc_next_phase;
	}
	SpinLockRelease(&fc_barrier->mutex);

	/*
	 * 如果我们是最后一个到达的预期参与者，
	 * 我们可以释放我们的同伴并返回true以表明这个后端被选中执行任何串行工作。
	 */
	if (fc_release)
	{
		ConditionVariableBroadcast(&fc_barrier->condition_variable);

		return true;
	}

	/*
	 * 否则，我们必须等待最后一个参与者到达并推进阶段。
	 */
	fc_elected = false;
	ConditionVariablePrepareToSleep(&fc_barrier->condition_variable);
	for (;;)
	{
		/*
		 * 我们知道阶段必须是start_phase，表示我们
		 * 需要继续等待，或者是next_phase，表示我们等待的最后一个
		 * 参与者要么已经到达，要么已经分离，所以下一个阶段已经开始。
		 * 该阶段不能进一步推进，因为这个后端是附加的。
		 */
		SpinLockAcquire(&fc_barrier->mutex);
		Assert(fc_barrier->phase == fc_start_phase || fc_barrier->phase == fc_next_phase);
		fc_release = fc_barrier->phase == fc_next_phase;
		if (fc_release && fc_barrier->elected != fc_next_phase)
		{
			/*
			 * 通常，最后到达并释放其他后端的后端被选中返回true（见上文），
			 * 这样它可以在拥有CPU时间片时开始处理串行工作。
			 * 但是，如果因为某人分离而推进了屏障，则需要选举
			 * 醒来的后端之一。
			 */
			fc_barrier->elected = fc_barrier->phase;
			fc_elected = true;
		}
		SpinLockRelease(&fc_barrier->mutex);
		if (fc_release)
			break;
		ConditionVariableSleep(&fc_barrier->condition_variable, fc_wait_event_info);
	}
	ConditionVariableCancelSleep();

	return fc_elected;
}

/*
 * 到达此屏障，但分离而不是等待。如果调用者是
 * 最后一个分离的参与者，则返回true。
 */
bool BarrierArriveAndDetach(Barrier *fc_barrier)
{
	return fc_BarrierDetachImpl(fc_barrier, true);
}

/*
 * 到达一个屏障，并分离除最后一个到达的参与者以外的所有人。
 * 如果调用者是最后一个到达的，因此仍然附加，则返回true。
 */
bool BarrierArriveAndDetachExceptLast(Barrier *fc_barrier)
{
	SpinLockAcquire(&fc_barrier->mutex);
	if (fc_barrier->participants > 1)
	{
		--fc_barrier->participants;
		SpinLockRelease(&fc_barrier->mutex);

		return false;
	}
	Assert(fc_barrier->participants == 1);
	++fc_barrier->phase;
	SpinLockRelease(&fc_barrier->mutex);

	return true;
}

/*
 * 附加到一个屏障。所有等待的参与者现在将等待此
 * 参与者调用BarrierArriveAndWait()、BarrierDetach()或
 * BarrierArriveAndDetach()。返回当前阶段。
 */
int BarrierAttach(Barrier *fc_barrier)
{
	int			fc_phase;

	Assert(!fc_barrier->static_party);

	SpinLockAcquire(&fc_barrier->mutex);
	++fc_barrier->participants;
	fc_phase = fc_barrier->phase;
	SpinLockRelease(&fc_barrier->mutex);

	return fc_phase;
}

/*
 * 从屏障分离。如果有其他等待者，
 * BarrierArriveAndWait()，如果他们只是等待这个后端，则可以推进阶段并释放他们。
 * 如果这个参与者是最后一个分离，则返回true。
 */
bool BarrierDetach(Barrier *fc_barrier)
{
	return fc_BarrierDetachImpl(fc_barrier, false);
}

/*
 * 返回屏障的当前阶段。调用者必须已附加。
 */
int BarrierPhase(Barrier *fc_barrier)
{
	/*
	 * 可以在不加锁的情况下读取barrier->phase，因为它不能改变
	 * 而没有我们（我们附加在上），并且在我们
	 * 附加或最后一次参与更改时执行了内存屏障。
	 */
	return fc_barrier->phase;
}

/*
 * 返回当前附加到此屏障的参与者数量的瞬时快照。
 * 仅用于调试目的。
 */
int BarrierParticipants(Barrier *fc_barrier)
{
	int			fc_participants;

	SpinLockAcquire(&fc_barrier->mutex);
	fc_participants = fc_barrier->participants;
	SpinLockRelease(&fc_barrier->mutex);

	return fc_participants;
}

/*
 * 从屏障分离。如果'到达'为true，则如果没有其他参与者，
 * 也增加阶段。如果有其他参与者等待，那么阶段将被推进，
 * 如果他们只是等待调用者，则将释放他们。 如果这个参与者是
 * 最后一个分离的，则返回true。
 */
static inline bool fc_BarrierDetachImpl(Barrier *fc_barrier, bool fc_arrive)
{
	bool		fc_release;
	bool		fc_last;

	Assert(!fc_barrier->static_party);

	SpinLockAcquire(&fc_barrier->mutex);
	Assert(fc_barrier->participants > 0);
	--fc_barrier->participants;

	/*
	 * 如果有其他参与者等待，并且我们是最后一个等待的参与者，则释放他们。
	 * 如果没有其他参与者在等待，但这是一个BarrierArriveAndDetach()调用，
	 * 则也推进阶段。
	 */
	if ((fc_arrive || fc_barrier->participants > 0) &&
		fc_barrier->arrived == fc_barrier->participants)
	{
		fc_release = true;
		fc_barrier->arrived = 0;
		++fc_barrier->phase;
	}
	else
		fc_release = false;

	fc_last = fc_barrier->participants == 0;
	SpinLockRelease(&fc_barrier->mutex);

	if (fc_release)
		ConditionVariableBroadcast(&fc_barrier->condition_variable);

	return fc_last;
}
